﻿#include<iostream>
#include<string>
using namespace std;

template<class  K>
struct avltreenode
{
	avltreenode<K>* _left;
	avltreenode<K>* _right;
	avltreenode<K>* _parent;
	K _key;
	int _bf;
	avltreenode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		,_parent(nullptr)
		, _key(key)
		,_bf(0)

	{}



};

template<class  K>
class avltree
{
	typedef  avltreenode<K> node;
public:
	void spinleft(node* parent)
	{
		node* subr = parent->_right;
		node* subrl = subr->_left;
		
		parent->_right = subrl;
		if (subrl)
			subrl->_parent = parent;

		subr->_left = parent;
		node* ppnode = parent->_parent;
		parent->_parent = subr;

		


		if (ppnode == nullptr)
		{

			_root = subr;
			subr->_parent = nullptr;


		}
		else
		{

			if (ppnode->_left == parent)
			{
				ppnode->_left=subr;
				subr->_parent = ppnode;

			}
			else
			{

				ppnode->_right=subr;
				subr->_parent = ppnode;


			}


		}




	
	
	
		subr->_bf = 0;
		parent->_bf = 0;
	
	}
	void spinright(node* parent)
	{
	
		node* subl = parent->_left;
		node* sublr = subl->_right;
		


		parent->_left = sublr;
		if (sublr)
			sublr->_parent = parent;



		subl->_right = parent;
		node* ppnode = parent->_parent;
		parent->_parent = subl;

		if (ppnode == nullptr)
		{

			_root = subl;
			subl->_parent = nullptr;


		}
		else
		{

			if (ppnode->_left == parent)
			{
				ppnode->_left=subl;
				subl->_parent = ppnode;

			}
			else
			{

				ppnode->_right=subl;
				subl->_parent = ppnode;


			}


		}

	
	
	
		subl->_bf = 0;
		parent->_bf = 0;
	
	
	
	}

	void spinlr(node* parent)
	{ 
		node* subl = parent->_left;
		node* sublr = subl->_right;
		int bf = sublr->_bf;

		spinleft(parent->_left);
		spinright(parent);
	    


		if (bf == 1)
		{
			subl->_bf = -1;
			sublr->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{

			subl->_bf = 0;
			sublr->_bf = 0;
			parent->_bf = 1;



		}
		else
		{
			subl->_bf = 0;
			sublr->_bf = 0;
			parent->_bf = 0;

		}
        
	}
	void spinrl(node* parent)
	{
		node* subr = parent->_right;
		node* subrl = subr->_left;
		int bf = subrl->_bf;
	
	
		spinright(subr);
		spinleft(parent);
		if (bf == 1)
		{

			parent->_bf = -1;
			subr->_bf = 0;
			subrl->_bf = 0;
		}
		else if (bf == -1)
		{
		
			parent->_bf = 0;
			subr->_bf = 1;
			subrl->_bf = 0;
		

		}
		else
		{
			subr->_bf = 0;
			subrl->_bf = 0;
			parent->_bf = 0;

		}
	}

	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new node(key);
			return true;

		}
		node* cur = _root;
		node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;


			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;



			}
			else
			{

				return false;
			}







		}
		cur = new node(key);
		if (parent->_key > key)
		{
			parent->_left = cur;



		}
		else
		{

			parent->_right = cur;


		}
		cur->_parent = parent;
		

		while (parent)
		{
			if (cur == parent->_left)
			{

				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;


			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				if (parent->_bf == 2 && cur->_bf == 1)//左旋
				{

					spinleft(parent);


				}
				else if (parent->_bf == 2 && cur->_bf == -1)//先左旋后右旋
				{
					spinrl(parent);
					



				}
				else if (parent->_bf == -2 && cur->_bf == -1)//右旋
				{
					 spinright(parent);

				}
				else//先右旋后左旋
				{
					spinlr(parent);



				}

				break;
			}
		








		}















		return true;

	}
	 
	bool IsBalanceTree()
	{
	
		return _IsBalanceTree(_root);
	
	
	
	

	}









	void inorder()
	{

		_inorder(_root);


	}
	void _inorder(node* root)
	{
		if (root == nullptr)
			return;

		_inorder(root->_left);
		cout << root->_key << " :"<<root->_bf<<endl;
		_inorder(root->_right);

	}

	




private:


	int treeheight(node* root)
	{
		if (root == nullptr)
			return 0;
		int leftheight = treeheight(root->_left);
		int rightheight = treeheight(root->_right);
		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
	
	}






	bool _IsBalanceTree(node*root)
	{
		if (root == nullptr)
			return true;

		int leftheight = treeheight(root->_left);
		int rightheight = treeheight(root->_right);

	   

		return (abs(rightheight - leftheight) < 2) && _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);


		





	}




	node* _root = nullptr;




};
int main()
{
	avltree<int>st;
	int a[] = //{ 16,3,1 };//测试右旋
	          //{ 16,32,58 };//测试左旋
		//{ 8,3,1,10,6,4};//测试右左旋

		{ 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
		// { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//{ 8,3,1,10,6,4,7,14,13 };
	for (auto e : a)
	{
		st.insert(e);
		
		

	}

    st.inorder();
	int ret=st.IsBalanceTree();
	cout << endl;
	cout << ret;






}